#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Queue.h"
#include "Stack.h"

#define SIZE 10

#define INFINITE 65536

typedef int DataType;

struct MGraph 
{
    DataType Vertex[SIZE];
    int Edge[SIZE][SIZE];
};

typedef struct MGraph MGraph;

void InitGraph(MGraph *G)
{
    int i, j;
    srand((unsigned int)time(NULL));

    //Initialize vertexes
    for ( i = 0; i < SIZE; ++i )
    {
        G->Vertex[i] = i;

        //Initialize edges
        for ( j = 0; j < SIZE; ++j )
        {
            G->Edge[i][j] = 0;
        }
    }
}

void Connect(MGraph *G, int i, int j)
{
    G->Edge[i][j] = G->Edge[j][i] = 1;
}

int IsConnected(MGraph *G, int i, int j)
{
    return G->Edge[i][j] == 1 && G->Edge[j][i] == 1;
}

void BFS(MGraph *G, int i)
{
    int k;
    Queue Q;
    int visited[SIZE] = {0};
    InitQueue(&Q);

    EnQueue(&Q, i);

    while ( !EmptyQueue(&Q) )
    {
        //find all siblings
        i = DeQueue(&Q);
        for ( k = 0; k < SIZE; ++k )
        {
            if ( IsConnected(G, i, k) && !visited[k] )
            {
                printf("%d\n", G->Vertex[k]);
                visited[k] = 1;
                EnQueue(&Q, k);
            }
        }
    }
}


void DFS(MGraph *G, int i)
{
    int k;
    Stack S;
    int visited[SIZE] = {0};

    InitStack(&S);

    PushStack(&S, i);

    while ( !EmptyStack(&S) )
    {
        i = PopStack(&S);
        for ( k = 0; k < SIZE; ++k )
        {
            if ( IsConnected(G, i, k) && !visited[k] )
            {
                printf("%d\n", G->Vertex[k]);
                visited[k] = 1;
                PushStack(&S, k);
                i = k;
                k = 0;
            }
        }

    }
}

//piece of crap...
int Dijkstra(MGraph *G, int i, int j)
{
    int t;
    int w = 0;
    int k;
    int path[SIZE] = { 0 };
    int distance = 0;
    int found = 0;
    int finish = 0;
    int exsit = 0;
    static int minw = INFINITE, min;
    path[w++] = i;

    //for each edge
    while ( !finish )
    {
        for ( k = 0; k < SIZE; ++k )
        {
            if ( IsConnected(G, i, k) )
            {
                //already exist
                exsit = 0;
                for ( t = 0; t < w; ++t )
                {
                    if ( k == path[t] )
                    {
                        exsit = 1;
                    }
                }

                if ( exsit )
                {
                    continue;
                }

                if ( G->Edge[i][k] < minw )
                {
                    minw = G->Edge[i][k];
                    min = k;
                    found = 1;
                }
            }
        }

        if ( found )
        {
            path[w++] = min;
            i = min;
            distance += minw;
            found = 0;
            minw = INFINITE;

            if ( i == j )
            {
                finish = 1;
            }
        }
    }

    return distance;
}